package 力扣._00周赛._430周赛.问题3;

import java.util.*;

class Solution {
    public long numberOfSubsequences(int[] nums) {
        int n = nums.length;
        long count = 0;

        // 创建映射来记录乘积的索引列表
        Map<Integer, List<int[]>> productMap = new HashMap<>();

        // 遍历所有可能的组合，寻找满足条件的子序列
        for (int p = 0; p < n; p++) {
            for (int r = p + 4; r < n; r++) {
                int productPR = nums[p] * nums[r];
                productMap.putIfAbsent(productPR, new ArrayList<>());
                productMap.get(productPR).add(new int[]{p, r});
            }
        }
        productMap.forEach((k, v) -> System.out.println(k + " : " + v.size()));

        // 再次遍历
        Set<Integer> keySet = productMap.keySet();
        for(int sum : keySet) {
            List<int[]> list = productMap.get(sum);
            for(int i = 0; i < list.size(); i++) {
                int[] pair1 = list.get(i);
                for(int j = i + 1; j < list.size(); j++) {
                    int[] pair2 = list.get(j);
                    if(pair2[0] > pair1[1])
                        break;
                    if( pair1[0] +1 < pair2[0]&&
                            pair2[0] +1 < pair1[1]&&
                            pair1[1] +1  < pair2[1]

                    ) {
                        if(count%1000000000==0){
                            System.out.println(list.size());
                            System.out.printf("%d %d %d %d\n", pair1[0], pair2[0], pair1[1], pair2[1]);
                        }
                        count++;
                    }
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        // 随机生成一个数组，长度为1000
        Random random = new Random();
        int[] nums = new int[1000];
        for (int i = 0; i < 1000; i++) {
            nums[i] = random.nextInt(1) + 1;
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(s.numberOfSubsequences(nums));
    }
}